package com.cat.dataStructure;

import java.util.*;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/properties-graph/description/
 * @create 2025/9/23 19:20
 * @since JDK17
 */

public class Solution71 {
    int[] f;
    int ans;
    Set<Integer>[] sets;

    int find(int x) {
        if (x != f[x]) {
            f[x] = find(f[x]);
        }
        return f[x];
    }

    void merge(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            f[fx] = fy;
            ans--;
        }
    }

    boolean judge(int i, int j, int k) {
        int cnt = 0;
        for (int key : sets[i]) {
            if (sets[j].contains(key)) {
                cnt++;
            }
        }
        return cnt >= k;
    }

    public int numberOfComponents(int[][] properties, int k) {
        int n = properties.length;
        ans = n;
        f = new int[n];
        sets = new HashSet[n];
        Arrays.setAll(sets, i -> new HashSet<>());
        for (int i = 0; i < n; i++) {
            f[i] = i;
            for (var num : properties[i]) {
                sets[i].add(num);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (judge(i, j, k)) {
                    merge(i, j);
                }
            }
        }

        return ans;
    }
}
